class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        int sizeOfArr = arr.size();
        //检查无效输入
        if(sizeOfArr <= 0 || k <= 0 || k > sizeOfArr)  return {};
        /*
        排序后查找，需要修改输入的数组(使用快排),查找到下标为k结果为止
        时间复杂度O(n)
        */
        int begin = 0;
        int end = sizeOfArr - 1;
        int findK = partition(arr, begin, end);

        while(findK != k - 1){
            if(findK < k - 1){
                begin = findK + 1;
                findK = partition(arr, begin, end);
            }else{
                end = findK - 1;
                findK = partition(arr, begin, end);
            }
        }

        int result = findK;
        if(!checkResult(arr, result))  result = 0;

        vector<int> returnInt;
        for(int i = 0; i <= result; ++i)  returnInt.push_back(arr[i]);

        return returnInt;

    }

    //随机数快速排序
    int partition(vector<int>& nums, int begin, int end){
        if(begin > end)  return begin;
        int index = RandomInRange(begin, end);
        if(index != end)  swap(nums[index], nums[end]);
        int small = begin - 1;//指向小于或等于参考值的最左侧

        for(index = begin; index < end; ++index){
            if(nums[index] < nums[end]){
                ++small;
                if(small != index)  swap(nums[small], nums[index]);
            }
        }

        if(++small != end)  swap(nums[small], nums[end]);
        return small;
    }

    //利用系统时间作为种子，产生[begin, end]之间的随机整数，但对于有大量重复元素的数组排序太慢
    int RandomInRange(int begin, int end){
        srand((unsigned)time(NULL));
        return (rand() % (end - begin + 1)) + begin;
    }

    bool checkResult(vector<int>& arr, int result){
        for(int i = 0; i <= result; ++i){
            if(arr[i] > arr[result])  return false;
        }
        return true;
    }
};

/**********************************************************************************************/
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        int sizeOfArr = arr.size();
        //检查无效输入
        if(sizeOfArr <= 0 || k <= 0 || k > sizeOfArr)  return {};
        /*
        不需要修改数组的时间复杂度O(nlogK)的算法：(特别适合处理海量数据)
        利用数组实现：由于每次插入时间复杂度为O(k)，因此总体时间复杂度为O(n*k)
        根据数据特点，将arr前k个数组重新创建一个新数组，从arr第k+1个数开始，逐一与新数组中每个元素进行比较，
        将新数组中所有大于该arr中元素的替换出来，确保每一次对比之后新数组中均为已对比的前段数组中最小的k个值
        */
        vector<int> result;
        for(int i = 0; i < k; ++i)  result.push_back(arr[i]);
        for(int i = k; i < sizeOfArr; ++i){
            int pivot = arr[i];
            int n = 0;
            while(n < k){
                if(result[n] > pivot){
                    //新数组每收进一个新值，都将自身最大的那个数替换出去
                    int temp = result[n];
                    result[n] = pivot;
                    pivot = temp;
                }
                ++n;
            }
        }
        return result;
    }
};

/***********************************************************************************************/
class Solution {
public:
    typedef multiset<int, greater<int>>  intSet;
    typedef multiset<int, greater<int>>::iterator  setIterator;

    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        int sizeOfArr = arr.size();
        //检查无效输入
        if(sizeOfArr <= 0 || k <= 0 || k > sizeOfArr)  return {};
        /*
        不需要修改数组的时间复杂度O(nlogK)的算法：(特别适合处理海量数据)
        利用数组实现：由于每次插入时间复杂度为O(k)，因此总体时间复杂度为O(n*k)
        根据数据特点，将arr前k个数组重新创建一个新数组，从arr第k+1个数开始，逐一与新数组中每个元素进行比较，
        将新数组中所有大于该arr中元素的替换出来，确保每一次对比之后新数组中均为已对比的前段数组中最小的k个值；
        利用基于红黑树的multiset：查找、删除和插入操作都只需要O(logk)的时间
        */
        intSet leastNumbers;
        vector<int>::const_iterator iter = arr.begin();
        for(; iter != arr.end(); ++iter){
            if(leastNumbers.size() < k)  leastNumbers.insert(*iter);
            else{
                setIterator iterGreastest = leastNumbers.begin();
                //容器已满后，若*iter小于最大值，将删除最大值并将*iter插入
                if(*iter < *(leastNumbers.begin())){
                    leastNumbers.erase(iterGreastest);
                    leastNumbers.insert(*iter);
                }
            }
        }

        vector<int> result;
        //将multiset中内容转换入数组
        setIterator iterSmallest = leastNumbers.begin();
        for(; iterSmallest != leastNumbers.end(); ++iterSmallest){
            result.push_back(*iterSmallest);
        }
        return result;
    }
};